// https://leetcode.cn/problems/sort-array-by-parity-ii/
// Created by ade on 2022/8/22.
// 给定一个非负整数数组 nums，  nums 中一半整数是 奇数 ，一半整数是 偶数 。
// 对数组进行排序，以便当 nums[i] 为奇数时，i 也是 奇数 ；当 nums[i] 为偶数时， i 也是 偶数 。
// 你可以返回 任何满足上述条件的数组作为答案 。

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

class Solution {
public:
    // 0 1 2 3 4 5
    // 4,0,0,1,1,1
    // 4,1,0,1,0,1 f
    // 4,1,0,1,0,1 c
    vector<int> sortArrayByParityII(vector<int> &nums) {
        partition(nums.begin(), nums.end(), [&](int x) {
            return x % 2 == 0;
        });

        int len = nums.size();
        int mid = len / 2;
        for (int i = 1; i < mid; i = i + 2) {
            if (mid % 2 == 1) {
                swap(nums[i], nums[len / 2 + i]);
            } else {
                swap(nums[i], nums[len / 2 + i - 1]);
            }
        }
        return nums;
    }
};

int main() {
    Solution so;
    vector<int> nums = {4, 1, 1, 0, 1, 0};
    auto a = so.sortArrayByParityII(nums);
    for (auto i : a) {
        cout << i << ",";
    }
    cout << endl;
    return 0;
}